動態規劃(Dynamic Programming,DP)的核心本質，是將一個複雜的大問題，拆解為數個相互重疊的子問題，並透過記錄已求解的答案來消除重複計算。

三核心前提

1. 最優子結構：
   原問題的整體最佳解為子問題的最優解。
2. 重疊子問題：
   大問題拆解出來的子問題，在求解過程中會被重複計算。
3. 無後效性：
   某狀態以後的階段發展，僅取決於當前狀態，與過去如何到達該狀態無關。

核心三步

1.狀態定義

明確dp陣列架構及意義(ex:1D陣列、2D陣列)。

2.邊界條件

初始基礎狀態
通常是定義dp[0]、dp[1]

3.狀態轉移

主要就是階段之間的邏輯推導
其中轉移的方法被叫狀態轉移方程，也是動態規劃最核心的地方

基本範例-費氏數列

網路上很多文章都用費氏數列作為動態規劃教學的第一個範例，這裡就主要說上面的三步定義

1. 狀態定義 - 一維陣列 dp[n] dp[x] 定義為費氏數列第x個數
2. 邊界條件 - dp[0]=0 dp[1]=1
3. 狀態轉移方程 - dp[i]=dp[i-1]+dp[i-2]

Cpp範例：

long long fibonacciWithArray(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    // 狀態定義
    std::vector<long long> dp(n + 1, 0);
    // 邊界條件
    dp[0] = 0;
    dp[1] = 1;
    // 狀態轉移
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
    }
}
// by ai

明眼人都看的出來費氏數列的第n項就是n-1項+n-2項，由此就能知道狀態轉移方程：dp[i]=dp[i-1]+dp[i-2]
也就是說能夠用3個變數就做出這個轉移：

long long fibonacciOptimized(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;

    // 只保留前兩項與當前項
    long long prev2 = 0; // 代表 dp[i-2]
    long long prev1 = 1; // 代表 dp[i-1]
    long long current = 0; // 代表 dp[i]

    // 滾動更新變數
    for (int i = 2; i <= n; ++i) {
        current = prev1 + prev2; // 狀態轉移方程式
        prev2 = prev1;           // 往後移一格
        prev1 = current;         // 往後移一格
    }
}
//by ai

另一個例子-Dice Combinations

先定義好上面三步

1. 一維陣列dp[n] dp[x]定義為湊出總和為x的方法數
2. 邊界條件：dp[0]=1 (因為從0開始，並讓dp[0]能夠作為dp[1]的轉移條件)
3. 前6項的總和(因為方法只會有前面幾次+(1~6)的可能)

dp[0]=1;//邊界條件
for(int i=1;i<=n;i++){
    for(int j=1;j<=6 && i-j>=0;j++){// 取前6項的總和(完成狀態轉移方程)
        dp[i]+=dp[i-j];
        dp[i]%=(int)(1e9+7);
    }
}

與費氏數列相同，動態規劃未必需要長度為 n 的陣列空間，其空間複雜度常有進一步壓縮的優化餘地。

後續將藉由實際題目的拆解，剖析動態規劃更複雜的變化。